package main

import (
	"fmt"
)

/*
一根长rope的绳子，去框nums数组中的顺序一维坐标，
求最多能框到数组中的几个坐标
*/
func dichotomyCoverMax(nums []int, rope int) int {
	var less int
	var r int
	var max int
	for r <= len(nums)-1 {
		less = findLess(nums, r, rope, less)
		fmt.Println("less ", less, "max ", r-less+1)
		max = Max(max, r-less+1)
		r++
	}
	return max
}

func findLess(nums []int, right int, rope int, less int) int {
	left := less
	cur := nums[right] - rope
	for right - left > 0 {
		mid := (right - left) >> 1 + left
		if nums[mid] < cur {
			left = mid+1
		} else if nums[mid] > cur {
			right = mid
		} else {
			return mid
		}
		s++
	}
	return right
}

func CoverMax(nums []int, rope int) int {
	var l int
	var r int
	var max int
	for r < len(nums) {
		if nums[r] - nums[l] <= rope {
			r++
			fmt.Print(r-l, " ")
		} else {
			r--
			l++
		}
		if l > r {
			r = l
		}
		max = Max(max, r-l)
		// fmt.Print(max)
		s++
	}

	//优化
	fmt.Println()
	l = 0
	r = 0
	max = 0

	for l < len(nums) {
		for (r < len(nums) && nums[r] - nums[l] <= rope) {
			r++
			fmt.Print(r-l, " ")
		}
		max = Max(max, r - l)
		// fmt.Print(max)
		l++
		s++
	}
	return max
}

var s int

func Max(a int, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	nums := []int{1,2,3,6,8,9,10,15,30,60,90,91,92,120,130}
	res := dichotomyCoverMax(nums, 24)
	fmt.Println(res)
	fmt.Println(s)
}